# NODE: 根据状态转移方程来确定入口，若状态转移方程当前最优解依赖后面状态，如第一道题，则递归入口在一开始。反之则反，如第二题。

# source:https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/ DP 记忆化搜索
from functools import cache
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        @cache
        def dfs(i):
            if i * 2 >= len(prices):
                return prices[i-1]
            res = inf
            for ind in range(i+1, i+i+2):
                res = min(res, dfs(ind))
            return res + prices[i-1]

        return dfs(1)
# 法二：DP 
class Solution:
    def minimumCoins(self, f: List[int]) -> int:
        n = len(f)
        for i in range((n+1)//2-1, 0, -1):
            f[i-1] += min(f[i:2*i+1])
        return f[0]

# source:https://leetcode.cn/problems/min-cost-climbing-stairs/ DP 记忆化搜索
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dfs(i):
            if i == 0 or i == 1:
                return cost[i]
            return cost[i] + min(dfs(i-2), dfs(i-1)) if i < len(cost) else min(dfs(i-2), dfs(i-1))
        return dfs(len(cost))